package triIndex.btree;

import java.util.*;
import transaction.*;
import triStorage.*;
import triDataStruct.*;

public class BNode extends BufferObject {
	
	public static final int LEAF = 0;
	public static final int BRANCH = 1;

	int order;
	int leastChildNum;
	int childnum;
	
	Vector<Integer> keys;
	Vector<Integer> values;

	int nodeId;
	int nextNodeId;
	boolean isLeaf;
	
	NodeFactory factory;

	int index;
	
	//private RWLock lock;
	
	BNode(int index) {
		this.index = index;
		this.keys = new Vector<Integer>();
		this.values = new Vector<Integer>();
		
		//lock = new RWLock();
	}

	public void reset(boolean isLeaf, int order, int nodeId, int nextNodeId, NodeFactory factory) {
		this.order = order;
		this.leastChildNum = (order + 1) / 2;
		this.isLeaf = isLeaf;
		this.keys.clear();
		this.values.clear();
		this.nextNodeId = nextNodeId;
		this.nodeId = nodeId;
		this.factory = factory;
	}
	
	@Override
	public int getKey() {
		return nodeId;
	}
	
	public BNode[] insert(int key, int rid, Transaction tx) {
		lock.lockWrite(tx);
		try {
			BNode[] ret;
			if (isLeaf) 
				ret = insert_leaf(key, rid, tx);
			else
				ret = insert_branch(key, rid, tx);
			/*
			System.out.println(">>> with key = " + key + " <<<");
			for (int i = 0; i < ret.length; ++i)
				ret[i].output();
			System.out.println(">>>  <<<");*/
			return ret;
		}
		finally {
			lock.unlockWrite(tx);
		}
	}
	
	public int find(int key, Transaction tx) {
		lock.lockRead(tx);
		try {
			//output();
			if (isLeaf)
				return find_leaf(key, tx);
			else
				return find_branch(key, tx);
		}
		finally {
			lock.unlockRead(tx);
		}
	}
	
	public void flush(IWriter writer, Transaction tx) {
		if (isLeaf)
			flush_leaf(writer, tx);
		else
			flush_branch(writer, tx);
	}
	
	public void load(IReader reader) {
		nodeId = reader.readInt();
		int type = reader.readInt();
		
		isLeaf = (type == BNode.LEAF);
		if (isLeaf)
			load_leaf(reader);
		else 
			load_branch(reader);
	}
	
	private int find_leaf(int key, Transaction tx) {
		//System.out.println("find_leaf " + key);
		for (int i = 0; i < childnum; ++i) {
			//System.out.println("keys <" + i + "> = " + keys.get(i));
			if (key < keys.get(i))
				return BTree.ERROR_CODE;
			else if (key == keys.get(i))
				return values.get(i);
		}
		
		return BTree.ERROR_CODE;
	}
	
	private int find_branch(int key, Transaction tx) {
		for (int i = 0; i < childnum; ++i)
			if (i == childnum - 1 || key <= keys.get(i)) {
				BNode child = getChild_branch(i, tx);
				int ret = child.find(key, tx);
				factory.unPin(child);
				
				return ret;
			}
		return BTree.ERROR_CODE;
	}
	
	private BNode getChild_branch(int index, Transaction tx) {
		BNode child = factory.getNode(values.get(index), this.order, tx);
		return child;
	}
	
	private BNode[] insert_leaf(int key, int value, Transaction tx) {
		int index;
		for (index = 0; index < childnum; ++index)
			if (key < keys.get(index))
				break;
		
		keys.add(index, key);
		values.add(index, value);
		childnum++;
		
		BNode[] ret;
		
		if (childnum > order)
			ret = split_leaf(tx);
		else {
			ret = new BNode[1];
			ret[0] = this;
		}
		
		return ret;
	}

	private BNode[] insert_branch(int key, int value, Transaction tx) {
		int index;
		for (index = 0; index < childnum - 1; ++index)
			if (key < keys.get(index))
				break;

		/*
		if (index < childnum - 1)
			System.out.println("Bbranch " + "insert into " + index + " " + keys.get(index).toString());
		else System.out.println("Bbranch " + "insert into " + index);
		*/
		
		BNode child = getChild_branch(index, tx);
		BNode[] nodes = child.insert(key, value, tx);

		if (nodes.length > 1) {
			++childnum;
			//System.out.println(nodes[0].nodeId + " " + nodes[1].nodeId);
			//System.out.println("split... " + this.nodeId + " ... "+ index + " : " + keys.size() + " " + values.size() + " " +
			//childnum);
			values.add(index + 1, nodes[1].nodeId);

			if (nodes[0].isLeaf && nodes[1].isLeaf) 
				keys.add(index, nodes[0].keys.lastElement());
			else if (!nodes[0].isLeaf && !nodes[1].isLeaf)
				keys.add(index, nodes[0].keys.remove(nodes[0].keys.size() - 1));
			else 
				System.err.println("should not be reached ! " + "index.btree.Branch");
			
			factory.save(nodes[0], tx);
			factory.save(nodes[1], tx);
			
			factory.unPin(nodes[0]);
			factory.unPin(nodes[1]);
		}
		else {
			factory.save(nodes[0], tx);
			factory.unPin(nodes[0]);
		}

		BNode[] ret;
		if (childnum - 1 > order) 
			ret = split_branch(tx);
		else {
			ret = new BNode[1];
			ret[0] = this;
		}
		return ret;
	}
	
	private BNode[] split_leaf(Transaction tx) {
		BNode leaf = factory.createNewLeaf(this.order, this.nextNodeId, tx);
		nextNodeId = leaf.nodeId;

		for (int i = leastChildNum; i < childnum; ++i) {
			leaf.keys.add(keys.remove(leastChildNum));
			leaf.values.add(values.remove(leastChildNum));
		}
		leaf.childnum = childnum - leastChildNum;
		childnum = leastChildNum;
		
		//System.out.println(leaf.childnum + " " + leaf.keys.size() + "......" + childnum + " " + keys.size());
		BNode[] ret = new BNode[2];
		ret[0] = this;
		ret[1] = leaf;
		
		return ret;
	}
	
	private BNode[] split_branch(Transaction tx) {
		BNode branch = factory.createNewBranch(this.order, tx);

		for (int i = leastChildNum; i < childnum - 2; ++i) {
			branch.keys.add(keys.remove(leastChildNum + 1));
			branch.values.add(values.remove(leastChildNum + 1));
		}
		branch.values.add(values.remove(leastChildNum + 1));
		
		branch.childnum = childnum - leastChildNum - 1;
		childnum = leastChildNum + 1;

		BNode[] ret = new BNode[2];
		ret[0] = this;
		ret[1] = branch;
		return ret;
	}
	
	private void flush_leaf(IWriter writer, Transaction tx) {
		writer.appendInt(nodeId, tx);
		writer.appendInt(BNode.LEAF, tx);
		writer.appendInt(nextNodeId, tx);
		writer.appendInt(childnum, tx);
		
		for (int i = 0; i < childnum; ++i) {
			writer.appendInt(keys.get(i), tx);
			writer.appendInt(values.get(i), tx);
		}
	}

	private void load_leaf(IReader reader) {
		this.nextNodeId = reader.readInt();
		this.childnum = reader.readInt();
		this.keys.clear();
		this.values.clear();
		//this.keys = new Vector<Integer>(childnum);
		//this.values = new Vector<Integer>(childnum);
		for (int i = 0; i < childnum; ++i) {
			keys.add(reader.readInt());
			values.add(reader.readInt());
		}
	}

	private void flush_branch(IWriter writer, Transaction tx) {
		writer.appendInt(nodeId, tx);
		writer.appendInt(BNode.BRANCH, tx);
		writer.appendInt(childnum, tx);
		
		for (int i = 0; i < childnum - 1; ++i) {
			writer.appendInt(values.get(i), tx);
			writer.appendInt(keys.get(i), tx);
		}
		writer.appendInt(values.get(childnum - 1), tx);
	}

	private void load_branch(IReader reader) {
		childnum = reader.readInt();
		
		keys.clear();
		values.clear();
		//keys = new Vector<Integer>(childnum - 1);
		//values = new Vector<Integer>(childnum);
		for (int i = 0; i < childnum - 1; ++i) {
			values.add(reader.readInt());
			keys.add(reader.readInt());
		}
		values.add(reader.readInt());
	}
	
	
	public void output() {
		if (isLeaf) 
			output_leaf();
		else 
			output_branch();
	}
	
	private void output_leaf() {
		System.out.println("*** Leaf " + this.nodeId + "***");
		for (int i = 0; i < this.childnum; ++i)
			System.out.print("(" + values.get(i) + ", " + keys.get(i) + ")  ");
		System.out.println();
	}
	
	private void output_branch() {
		System.out.println("*** Branch " + this.nodeId + "***");
		for (int i = 0; i < this.childnum - 1; ++i)
			System.out.print("(" + values.get(i) + ", " + keys.get(i) + ")  ");
		System.out.println(values.lastElement());
	}
}

